/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // if(lists.size() == 1 && lists[0] == NULL)
        //     return NULL;
        vector<int> nums;
        for(int i = 0; i < lists.size(); i++)
        {
            if(lists[i] == NULL)
            {
                lists.erase(lists.begin() + i);
                i--;
            }
            else
                nums.push_back(lists[i] -> val);
        }
        if(lists.empty())
            return NULL;
        
        auto iter = min_element(nums.begin(), nums.end());
        int index = distance(nums.begin(), iter);
        ListNode* root = lists[index];
        
        ListNode* currP;
        ListNode* prevP = root;
        
        while(true)
        {
            if (lists[index] -> next == NULL)
            {
                lists.erase(lists.begin()+index);
                nums.erase(nums.begin()+index);
                if(lists.empty())
                    return root;
            }
            else
            {
                lists[index] = lists[index] -> next;
                nums[index] = lists[index] -> val;
            }
                
            iter = min_element(nums.begin(), nums.end());
            index = distance(nums.begin(), iter);
            currP = lists[index];
            prevP -> next = currP;
            prevP = currP;
        }
    }
};
